; memory.asm
; memory management

	.export malloc
	.export mfree
	.export mgetfree
	.export mgetmax
	.export mgettotal
	
	.export initmem

	.include "global.inc"

	.import panic
	.import __RAM_LAST__

	.struct RamBlock
		start	.word
		size	.word
	.endstruct
	
	.struct MemChunk
		magic	.byte
		crc		.byte
		size	.word
		next	.word
	.endstruct

MC_HDRSIZE = .sizeof (MemChunk)
MC_MAGIC = $DD

	.segment	"ZEROPAGE"
	
memptr:		.res 2
prvptr:		.res 2

	.segment "DATA"

rootblk:	.tag MemChunk
	
firstfree = rootblk + MemChunk::next

freesize:	.word 0
totalsize:	.word 0

reqsize:	.word 0
remsize:	.word 0

tmpptr:		.res 2

	.segment "CODE"
	
malloc:		; alloc block of size A/X -> A/X .. ptr to memory or 0, Y .. scratch
			sta reqsize
			stx reqsize+1
			jsr firstblk
			beq @retnull
@srchblk:	jsr chksize
			bcs @found
@nextblk:	jsr nextblk
			bne @srchblk
@retnull:	lda #0
			tax
			rts
@found:		jsr unhookblk
			jsr chksplit
			clc
			lda memptr
			adc #MC_HDRSIZE
			tay
			lda memptr+1
			adc #0
			tax
			tya
			rts

mfree:		; free block in A/X
			sec
			sbc #MC_HDRSIZE
			sta memptr
			txa
			sbc #0
			sta memptr+1
			jsr chkblk
			jmp addfree

mgetfree:	; get free size in A/X
			lda freesize
			ldx freesize+1
			rts

mgettotal:	; get total size in A/X
			lda totalsize
			ldx totalsize+1
			rts

mgetmax:	; get biggest free block size in A/X
			lda #0					; (reqsize) := 0
			sta reqsize
			sta reqsize+1
			jsr firstblk
			beq @ret
@srchblk:	jsr chksize
			bcc @nextblk
			ldy #MemChunk::size		; (reqsize) := memptr->size
			lda (memptr), y
			sta reqsize
			iny
			lda (memptr), y
			sta reqsize+1
@nextblk:	jsr nextblk
			bne @srchblk
@ret:		lda reqsize
			ldx reqsize+1
			rts

chksplit:	; free excess bytes of block (memptr)
			; excess size in (remsize)
			; requested size in (reqsize)
			lda remsize+1
			bne @dosplit
			lda remsize
			cmp #MC_HDRSIZE*2
			bcc @done
@dosplit:	; init excess block
			jsr savmemptr
			clc
			lda memptr				; memptr += (reqsize)
			adc reqsize
			sta memptr
			lda memptr+1
			adc reqsize+1
			sta memptr+1
			clc
			lda memptr				; memptr += MC_HDRSIZE
			adc #MC_HDRSIZE
			sta memptr
			lda memptr+1
			adc #0
			sta memptr+1
			ldy #MemChunk::magic	; init block header
			lda #MC_MAGIC
			sta (memptr), y
			ldy #MemChunk::size
			sec
			lda remsize
			sbc #MC_HDRSIZE
			sta (memptr), y
			iny
			lda remsize+1
			sbc #0
			sta (memptr), y
			jsr addfree				; add to free list
			; reduce cur block size to reqsize
			jsr resmemptr
			ldy #MemChunk::size
			lda	reqsize
			sta (memptr), y
			iny
			lda	reqsize+1
			sta (memptr), y
			jsr updhdr
@done:		rts 

chkblk:		; check block header, "panic" if crc is wrong
			jsr calccrc
			cmp #0
			beq @ok
			jmp panic
@ok:		rts

savmemptr:	; tmpptr := memptr	
			lda memptr
			sta tmpptr
			lda memptr+1
			sta tmpptr+1
			rts

resmemptr:	; memptr := tmpptr
			lda tmpptr
			sta memptr
			lda tmpptr+1
			sta memptr+1
			rts

unhookblk:	; remove block from chain, update free size
			jsr savmemptr			; tmpptr := memptr
			ldy #MemChunk::next		; prvptr->next := memptr->next
			lda (memptr), y
			sta (prvptr), y
			iny
			lda (memptr), y
			sta (prvptr), y
			lda prvptr				; memptr := prvptr
			sta memptr
			lda prvptr+1
			sta memptr+1
			jsr updhdr				; update header(memptr)
			jsr resmemptr			; memptr := tmpptr
			ldy #MemChunk::next		; memptr->next = 0
			lda #0
			sta (memptr), y
			iny
			sta (memptr), y
			ldy #MemChunk::size		; freesize -= memptr->size
			sec
			lda freesize
			sbc (memptr), y
			sta freesize
			iny
			lda freesize+1
			sbc (memptr), y
			sta freesize+1
			jmp updhdr				; update header

chksize:	; check if (memptr) block is bigger than (reqsize) -> C 
			ldy #MemChunk::size
			lda (memptr), y
			sec
			sbc reqsize
			sta remsize
			iny
			lda (memptr), y
			sbc reqsize+1
			sta remsize+1
			rts			

firstblk:	; set pointers to first block in chain -> Z indicates NULL
			lda #<rootblk
			sta prvptr
			lda #>rootblk
			sta prvptr+1
			lda firstfree
			sta memptr
			lda firstfree+1
			sta memptr+1
			ora memptr		; set Z flag
			rts

nextblk:	; set pointers to next block in chain -> Z indicates NULL
			lda memptr
			sta prvptr
			lda memptr+1
			sta prvptr+1
			ldy #MemChunk::next
			lda (memptr), y
			tax
			iny
			lda (memptr), y
			sta memptr+1
			stx memptr
			ora memptr		; set Z flag
			rts

updhdr:		; update mem header (memptr)
			ldy #MemChunk::crc
			lda #0
			sta (memptr), y
			jsr calccrc
			ldy #MemChunk::crc
			sta (memptr), y
			rts

calccrc:	; calc crc for mem header (memptr)
			lda #0
			ldy #5
@nextcrc:	eor (memptr), y
			dey
			bpl @nextcrc
			rts

addfree:	; add memptr to free list
			ldy #MemChunk::next
			lda firstfree
			sta (memptr), y
			iny
			lda firstfree+1
			sta (memptr), y
			jsr updhdr
			lda memptr
			sta firstfree
			lda memptr+1
			sta firstfree+1
			; update total size of free memory
			ldy #MemChunk::size
			lda (memptr), y
			iny
			clc
			adc freesize
			sta freesize
			lda (memptr), y
			adc freesize+1
			sta freesize+1
			rts

	.segment "BOOT"

tmpsize:	.word $0000

maddram:	; A/X .. pointer to RamBlock, Y .. scratch
			; set memptr to RamBlock
			sta memptr
			stx memptr+1
			; get size, sub header size, save to tmpsize
			ldy #RamBlock::size
			lda (memptr), y
			sec
			sbc #MC_HDRSIZE
			sta tmpsize
			iny
			lda (memptr), y
			sbc #0
			sta tmpsize+1
			bcc @ignore	; less than header size -> ignore block
			; set memptr to block
			ldy #RamBlock::start
			lda (memptr), y
			tax
			iny
			lda (memptr), y
			sta memptr+1
			stx memptr
			; init block header
			ldy #MemChunk::magic
			lda #MC_MAGIC
			sta (memptr), y
			ldy #MemChunk::size
			lda tmpsize
			sta (memptr), y
			iny
			lda tmpsize+1
			sta (memptr), y
			; add to free list
			jmp addfree
@ignore:	rts

; search for RAM in $0400-$0FFF, __RAM_LAST__+1-$7FFF, $A000-$BFFF

sblklo:		.byte  <(__RAM_LAST__+1), $00, $00	
sblkhi:		.byte >(__RAM_LAST__+1),  $04, $A0
eblklo:		.byte $00, $00, $00
eblkhi:		.byte $80, $10, $C0

BLK_CNT = 3

curidx:		.byte BLK_CNT
blkflgs:	.byte 0

	FLAG_BLK04 = 1
	FLAG_BLKA0 = 2
	FLAG_BLKB0 = 4

prpscan:	; prepare memory scan
			lda $38			; get BASIC RAM end
			cmp sblkhi		; check if plausible
			bcc @scanvec
			sta eblkhi		; set as blk[0] end.
			lda $37
			sta eblklo
			; scan vectors
@scanvec:	lda #$15
			sta strptr
			lda #$03
			sta strptr+1
			ldy #28
@readvec:	lda (strptr), y
			; check target region
			cmp #$C0
			bcs @nextvec
			cmp #$A0
			bcc @chk3k
			cmp #$B0
			bcc @isa0
			lda blkflgs
			ora #FLAG_BLKB0
			sta blkflgs
			bne @nextvec
@isa0:		lda blkflgs
			ora #FLAG_BLKA0
			sta blkflgs
			bne @nextvec
@chk3k:		cmp #$10
			bcs @nextvec
			cmp #$04
			bcc @nextvec
			lda blkflgs
			ora #FLAG_BLK04
			sta blkflgs
			; next
@nextvec:	dey
			dey
			bpl @readvec
			; adjust blocklist
			lda blkflgs
			beq @prpdone
			and #(FLAG_BLKA0|FLAG_BLKB0)
			beq @chk04
			; TODO: keep A0 or B0
			dec curidx
@chk04:		lda blkflgs
			and #FLAG_BLK04
			beq @prpdone
			lda sblklo+2
			sta sblklo+1
			lda sblkhi+2
			sta sblkhi+1
			lda eblklo+2
			sta eblklo+1
			lda eblkhi+2
			sta eblkhi+1
			dec blkflgs
@prpdone:	rts

curblk:		.tag RamBlock

initmem:	jsr prpscan
			; init root block
			lda #MC_MAGIC
			sta rootblk+MemChunk::magic
			lda #0
			sta rootblk+MemChunk::crc
			sta rootblk+MemChunk::size
			sta rootblk+MemChunk::size+1
			sta rootblk+MemChunk::next
			sta rootblk+MemChunk::next+1
			; scan RAM blocks for memory
@nxtblk:	dec curidx
			bpl @chkblk
			lda freesize
			sta totalsize
			lda freesize+1
			sta totalsize+1
			rts
			; setup current block
@chkblk:	ldx curidx
			lda sblklo, x
			sta reg0
			sta curblk + RamBlock::start
			lda sblkhi, x
			sta reg0+1
			sta curblk + RamBlock::start+1
			lda eblklo, x
			sta reg1
			lda eblkhi, x
			sta reg1+1
			lda #0
			sta curblk + RamBlock::size
			sta curblk + RamBlock::size+1
			ldy #0
			; test write byte
@nxtbyt:	lda #$55
			sta (reg0), y
			cmp (reg0), y
			bne @endmem
			lda #$AA
			sta (reg0), y
			cmp (reg0), y
			bne @endmem
			; inc ptr & size
			inc curblk + RamBlock::size
			bne @noovl1
			inc curblk + RamBlock::size + 1
@noovl1:	inc reg0
			bne @noovl2
			inc reg0+1
@noovl2:	lda reg0+1
			cmp reg1+1
			bne @nxtbyt
			lda reg0
			cmp reg1
			bne @nxtbyt
@endmem:	lda #<curblk
			ldx #>curblk
			jsr maddram		
			jmp @nxtblk
